package sort.LinkedList;

import struct.ListNode;

/**
 * @description:
 * <br>链表插入排序
 * <br>时间复杂度：O(n^2)，其中 n 是链表的长度。
 * <br>空间复杂度：O(1)。
 * @author: mayunfei
 * @date: 2024/12/26 20:17
 */
public class LinkedListInsertionSort implements LinkedListSort {

    @Override
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode lastSorted = head;
        ListNode curr = head.next;
        while (curr != null) {
            if (curr.val < lastSorted.val) {
                ListNode pre = dummy;
                while (pre.next.val < curr.val) pre = pre.next;
                lastSorted.next = curr.next;
                curr.next = pre.next;
                pre.next = curr;
            } else {
                lastSorted = curr;
            }
            curr = lastSorted.next;
        }
        return dummy.next;
    }
}
